package seqlist.oj;

public class Num203 {
//    /**
//     *
//     * @param head 传入的链表头节点
//     * @param val 待删除的元素
//     * @return 删除后的链表头节点
//     */
//    public ListNode removeElements(ListNode head, int val) {
//        // 所有代码就可以在这个方法中实现
//        // 先判断边界条件
//        // 先判断头节点是否为空并且头节点刚好就是待删除的节点
//        while (head != null && head.val == val) {
//            ListNode node = head;
//            head = head.next;
//            node.next = null;
//        }
//        // 此时链表已经是个空链表了，直接return null
//        if (head == null) {
//            return null;
//        }else {
//            // 从头开始寻找值为val的节点
//            ListNode prev = head;
//            while (prev.next != null) {
//                if (prev.next.val == val) {
//                    // node就是待删除的节点
//                    ListNode node = prev.next;
//                    prev.next = node.next;
//                    node.next = null;
//                }else {
//                    prev = prev.next;
//                }
//            }
//            return head;
//        }
//    }
    // 虚拟头节点法
//    public ListNode removeElements(ListNode head, int val) {
//        ListNode dummyHead = new ListNode(-1);
//        // 与传入链表链接
//        dummyHead.next = head;
//        ListNode prev = dummyHead;
//        // prev是虚拟头节点，值不存在，从prev.next开始看元素值是否要删除
//        while (prev.next != null) {
//            // 此时prev就是待删除的节点
//            if (prev.next.val == val) {
//                ListNode node = prev.next;
//                prev.next = node.next;
//                node.next = null;
//            }else {
//                // 此时prev不是待删除节点的前驱，继续移动，向后判断
//                prev = prev.next;
//            }
//        }
//        return dummyHead.next;
//    }

    // 递归法
    // 传入一个链表，就能删除链表中所有值为val的节点，返回删除后的头节点
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 删除头节点之后的链表元素
        head.next = removeElements(head.next,val);
//        // 只需要判断头节点的情况
//        if (head.val == val) {
//            return head.next;
//        }
//        return head;
        return head.val == val ? head.next : head;
    }
}
